-- recursive copy
function deepcopy(orig)
    local orig_type = type(orig)
    local copy
    if orig_type == 'table' then
        copy = {}
        for orig_key, orig_value in next, orig, nil do
            copy[deepcopy(orig_key)] = deepcopy(orig_value)
        end
        setmetatable(copy, deepcopy(getmetatable(orig)))
    else -- number, string, boolean, etc
        copy = orig
    end
    return copy
end


-- create a circular doubly-linked list:
-- you can pass either a series of values or an array of values
function circularlist(...)
    local args = {...}
    if #args == 1 and type(args[1]) == "table" then args = {unpack(args[1])} end
    local i = 1
    local list = { value = args[i] }
    local current = list
    while i < #args do
            i = i+1
            current.next = { prev = current }
            current = current.next
            current.value = args[i]
    end
    current.next = list
    list.prev = current
    return list
end



-- http://roguebasin.roguelikedevelopment.org/index.php?title=LUA_2d_Line_of_sight
function lineofsight(x1,y1,x2,y2, isBlocked)
	local math = math
	local deltax = math.abs(x2 - x1) -- // The difference between the x's
	local deltay = math.abs(y2 - y1) -- // The difference between the y's
	local x = x1; -- // Start x off at the first pixel
	local y = y1; -- // Start y off at the first pixel
	local xinc1,xinc2,yinc1,yinc2

	if (x2 >= x1) then -- // The x-values are increasing
		xinc1 = 1;
		xinc2 = 1;
	else -- // The x-values are decreasing
		xinc1 = -1;
		xinc2 = -1
	end

	if (y2 >= y1) then -- // The y-values are increasing
		yinc1 = 1;
		yinc2 = 1;
	else -- // The y-values are decreasing
		yinc1 = -1;
		yinc2 = -1;
	end

	if (deltax >= deltay) then -- // There is at least one x-value for every y-value
		xinc1 = 0; -- // Don't change the x when numerator >= denominator
		yinc2 = 0; -- // Don't change the y for every iteration
		den = deltax;
		num = deltax / 2;
		numadd = deltay;
		numpixels = deltax; -- // There are more x-values than y-values
	else -- // There is at least one y-value for every x-value
		xinc2 = 0; -- // Don't change the x for every iteration
		yinc1 = 0; -- // Don't change the y when numerator >= denominator
		den = deltay;
		num = deltay / 2;
		numadd = deltax;
		numpixels = deltay; -- // There are more y-values than x-values
	end

	local onemoreround = 0
	local roundnum = 0

	local firstStep = nil

	while (true) do
		roundnum = roundnum + 1 --forces two distance sight
		           --  // Draw the current pixel
		if onemoreround == 1 and roundnum > 2 then return false end --this stuff is so it penetrates one round and doesnt stop on the first round
		if (roundnum ~= 1) and isBlocked(x,y) then onemoreround = 1 end --was return false
		if x == x2 and y == y2 then return true end

		num = num + numadd; --// Increase the numerator by the top of the fraction
		if (num >= den) then -- // Check if numerator >= denominator
			num = num - den; -- // Calculate the new numerator value
			x = x +xinc1; -- // Change the x as appropriate
			y = y+ yinc1; -- // Change the y as appropriate
		end
		x = x+xinc2; -- // Change the x as appropriate
		y = y+yinc2; -- // Change the y as appropriate
	end
end
